Shape data obtained by 3D measurement systems are often represented as distance images. In order to obtain the entire shape model from multiple measurement results, it is necessary to integrate these distance images. To integrate multiple distance data into a single shape, several types of approaches have been proposed, such as, stitching meshes at the overlapped surfaces (zippering) [Non Patent Literature 1], and methods using signed distance fields [Non Patent Literature 2]. Among them, the methods using signed distance fields have been widely researched because they are capable of processing a large volume of input data efficiently. A signed distance field is a scalar field defined for each voxel in 3D space such that the absolute value of the scaler is the distance between the voxel and the object surface and the sign of the scaler indicates whether the voxel is inside or outside of the object. Generally, isosurface satisfying signed distance value to be 0 defines an object's surface. Therefore, signed distance fields can be considered as one of the shape representation method. Signed distance fields have also been used for interpolating holes appearing in unmeasured parts of object surfaces.
Curless and Levoy filled holes of a measured shape by classifying each voxel in volume space as either Unseen (unseen regions), NearSurface (near the surfaces), or Empty (outside the object), and generating a mesh between Unseen and Empty regions [Non Patent Literature 1]. This process is known as space carving (henceforth abbreviated to SC) due to its resemblance to a process of carving the outside of the object in the volume. The SC method is capable of effectively interpolating missing parts when there is plenty of observed data. However, when only a few distance images are captured, the SC method often fails. This problem occurs because the target object and the “remains of carving” in volume space become connected.
One of the approaches to solve this problem would be classifying the Unseen voxels as either inside or outside of the object. Since Unseen voxels include both unobserved voxels inside an object (due to occlusion or low reflection) and voxels outside the object, it is necessary to distinguish these cases.
Regarding filling holes of the surface of the shape defined as isosurfaces of signed distance fields, a number of methods have already been proposed. Davis et al. presented a method for interpolating shape data expressed as an isosurface, in which signed distance field volume data is diffused using a smoothing filter and combined with the original signed distance field [Non Patent Literature 3].
In [Non Patent Literature 4] and [Non Patent Literature 5], interpolating scenes with complex objects by taking the consensus between each voxel in a signed distance field with its surrounding voxels was realized successfully. In [Non Patent Literature 6], the method for filling unmeasured regions by fitting quadrics to the gaps in the signed distance field was proposed.
In recent years, many methods have been proposed for utilizing the rapid improvement in the computational performance of GPUs for general calculations besides graphics. Nitschke et al. proposed a method for implementing 3D reconstruction from 2D contours using the SC method on GPUs [Non Patent Literature 7]. Also, For example, Sud et al., presented a high-speed method for calculating distance fields from object models using GPUs, and demonstrated that it could be used for measuring the distance between adjacent objects [Non Patent Literature 8].
In addition, there exist several patent literatures related to this patent, such as patent literatures from 1 to 7 as follows. Although those patents have in common with realizing 3D shape reconstruction, there exist obvious differences between those previous patents and the present invention, for example data is different and thereof.
In the patent literature 1, the method to reconstruct the shape of boundary from volume data is disclosed. Especially application for CT and MRI is disclosed.
In the patent literature 2, the technique to improve the reconstruction quality of the shape of thin part of the object when integrating multiple 3-dimensional data with volumetric method is disclosed.
In the patent literature 3, the image processing method on volume data which is reconstructed based on silhouette technique is disclosed.
In the patent literature 4, the method to improve the accuracy on shape integration of multiple 3D data using the value called vector potential instead of scalar value of volume (in the common literature) is disclosed.
In the patent literature 5, the method to improve the accuracy using the direction of the vector when 3D data are integrated by using vector potential in the patent literature 4 is disclosed.
In the patent literature 6, since an intermediate data is large before shape integration in the patent literature 4, the method to reduce the intermediate data is disclosed.
In the patent literature 7, the invention to utilize the shape integration method using volume (signed distance field) to stitch multiple shape data, those shapes are largely different each other, is disclosed.    [Non Patent Literature 1] B. Curless and M. Levoy: “A volumetric method for building complex models from distance images”, Computer Graphics, 30, Annual Conference Series, pp. 303-312 (1996).    [Non Patent Literature 2] G. Turk and M. Levoy: “Zippered polygon meshes from range images”, SIGGRAPH 1994: Proceedings of the 21st annual conference on Computer graphics and interactive techniques, New York, N.Y., USA, ACM Press, pp. 311-318 (1994).    [Non Patent Literature 3] J. Davis, S. R. Marschner, M. Gaff and M. Levoy: “Filling holes in complex surfaces using volumetric diffusion.”, 3DPVT, pp. 428-438 (2002).    [Non Patent Literature 4] R. Sagawa and K. Ikeuchi: “Taking consensus of signed distance field for complementing unobservable surface”, Proc. 3DIM 2003, pp. 410-417 (2003).    [Non Patent Literature 5] Ryusuke SAGAWA and Katsushi IKEUCHI: “Taking Consensus of Signed Distance Field for Hole Filling”, IEICE D, J88-D2,3, pp. 541-551 (2005).    [Non Patent Literature 6] T. Masuda: “Filling the signed distance field by fitting local quadrics”, 3DPVT '04: Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium on (3DPVT2004), Washington, D.C., USA, IEEE Computer Society, pp. 1003-1010 (2004).    [Non Patent Literature 7] C. NITSCHKE, A. NAKAZAWA and H. TAKEMURA: “Real-time space carving using graphics hardware”, MIRU 2006, pp. 928-933 (2006).    [Non Patent Literature 8] A. Sud, N. Govindaraju, R. Gayle and D. Manocha: “Interactive 3d distance field computation using linear factorization”, SI3D '06: Proceedings of the 2006 symposium on Interactive 3D graphics and games, New York, N.Y., USA, ACM Press, pp. 117-124 (2006).    [Non Patent Literature 9] W. E. Lorensen and H. E. Cline: “Marching cubes: A high resolution 3d surface construction algorithm”, SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques, Vol. 21, New York, N.Y., USA, ACM Press, pp. 163-169 (1987).    [Patent Literature 1] Japan Patent Application publication 2005-038219    [Patent Literature 2] Japan Patent Application publication 2003-058904    [Patent Literature 3] Japan Patent Application publication 2002-366934    [Patent Literature 4] Japan Patent Application publication 2000-111324    [Patent Literature 5] Japan Patent Application publication 2002-236936    [Patent Literature 6] Japan Patent Application publication 2002-056380    [Patent Literature 7] Japan Patent Application publication 2001-084403